package likou

// https://leetcode-cn.com/problems/palindrome-partitioning/

// 这道题相当于是对 字符串进行切割为 任意个子串，如果子串都是回文串就返回对应的切割序列。
// 那么使用树形结构去每次都可以切 小于 len(s) 长度的串。 再进行剪枝，判断
func partition(s string) [][]string {
	var dfs func(int, []string)
	var check func(string, int, int) bool
	var listS = make([][]string, 0)

	check = func(s string, i, j int) bool{
		for i < j {
			if s[i] != s[j] {
				return false
			}
			i ++
			j --
		}
		return true
	}

	dfs = func(startIndex int, path []string) {
		// 终止条件
		if startIndex == len(s) {
			// 拷贝slice
			temp := make([]string, len(path))
			copy(temp, path)
			listS = append(listS, temp)
			return
		}
		// 遍历每一个字符, 每一步可以切 0 - len(s) 长度
		for i := startIndex; i < len(s); i++ {
			endIndex := i
			// 剪枝：拿到对应的子字符串， 如果不是回文，就结束这轮循环
			if !check(s, startIndex, endIndex) {
				continue
			}
			// 取子字符串放到path 中
			path = append(path, s[startIndex: i + 1])
			dfs(i + 1, path)
			// 回溯，去掉path添加的子字符串
			path = path[:len(path) - 1]
		}
	}

	dfs(0, []string{})

	return listS
}